'''
Powell方法
Author：Xiao Tang
Time: 2024/12/6 09:59
Email: tangx73@mail2.sysu.edu.cn
'''

import numpy as np
from scipy.optimize import bracket
import matplotlib.pyplot as plt

def perform_line_search_golden_section(func, x, direction, tol=1e-5, max_iter=1):
    """
    使用黄金分割法进行线搜索，找到沿给定方向的最优步长。

    参数:
        func: 目标函数
        x: 当前点
        direction: 线搜索的方向
        tol: 收敛容忍度（默认值为1e-5）
        max_iter: 最大迭代次数（默认值为100）

    返回:
        alpha_opt: 最优步长
        fval_new: 新点处的函数值
    """
    # 黄金分割比
    phi = (1 + 5 ** 0.5) / 2

    # 初始化搜索区间
    a = 0
    b = 1
    c = b - (b - a) / phi
    d = a + (b - a) / phi

    # 计算初始点和中点的函数值
    f_c = func(x + c * direction)
    f_d = func(x + d * direction)

    iter_count = 0
    while abs(b - a) > tol and iter_count < max_iter:
        iter_count += 1

        if f_c < f_d:
            b = d
            d = c
            c = b - (b - a) / phi
            f_d = f_c
            f_c = func(x + c * direction)
        else:
            a = c
            c = d
            d = a + (b - a) / phi
            f_c = f_d
            f_d = func(x + d * direction)

    # 返回最优的步长和新点的函数值
    alpha_opt = (a + b) / 2
    fval_new = func(x + alpha_opt * direction)

    return alpha_opt, fval_new, a, b


def powell_algorithm(func, x0, epsilon=1e-6, maxiter=1000):
    """自定义的Powell算法，返回优化后的x和y以及目标函数值。

    Parameters
    ----------
    func : callable
        目标函数。
    x0 : ndarray
        初始猜测。
    epsilon : float, optional
        收敛容差，默认为 1e-6。
    maxiter : int, optional
        最大迭代次数，默认为 1000。

    Returns
    -------
    points : list
        包含优化结果的列表，points[0] 为优化后的 x，points[1] 为优化后的 y，points[2] 为函数值。
    """
    N = len(x0)
    x = np.array(x0, dtype=float)
    fval = func(x)
    direc = np.eye(N)  # 初始化为单位矩阵

    for iter in range(maxiter):
        fx = fval
        delta, bigind = 0.0, -1  # Step 2: 在每个方向上进行线搜索

        for i in range(N):
            direc1 = direc[i]
            alpha_opt, fval_new, _, _ = perform_line_search_golden_section(func, x, direc1)
            x_new = x + alpha_opt * direc1  # 计算新的位置
            change = fx - fval_new  # 使用已计算的新函数值

            if change > delta:  # 更新最大变化
                delta, bigind = change, i

            x = x_new  # 更新当前点
            fval = fval_new  # 更新函数值

        # 收敛检测
        norm_diff = np.linalg.norm(x - x0)
        if delta < epsilon and norm_diff < epsilon:
            break

        if delta < epsilon:  # 检查是否无显著更新
            break

        # 组合方向进行线搜索
        u = x - x0
        alpha_opt, fval_new, _, _ = perform_line_search_golden_section(func, x0, u)
        x_new = x0 + alpha_opt * u
        fval_new = func(x_new)

        if fval_new < fval:
            x = x_new
            fval = fval_new

        # 更新方向
        if iter % N == N - 1:
            if bigind >= 0:
                direc[bigind] = u / np.linalg.norm(u) if np.linalg.norm(u) != 0 else direc[bigind]
                new_direction = u - sum([np.dot(u, direc[j]) * direc[j] for j in range(N) if j != bigind])
                direc[bigind] = new_direction / np.linalg.norm(new_direction) if np.linalg.norm(new_direction) != 0 else \
                direc[bigind]

        x0 = x.copy()  # 更新上一个位置

    # 返回优化后的结果
    points = [x[0], x[1], fval]
    return points


# # 示例目标函数
# def func(x):
#     return x[0] ** 2 + x[1] ** 2
#
#
# # 初始猜测
# x0 = [1.0, 2.0]
#
# # 调用优化方法
# points = powell_algorithm(func, x0)
#
# # 打印结果
# print("优化后的 x 和 y:", points[0], points[1])
# print("当前函数值:", points[2])
